import offer.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: wangliuyang
 * @Date: 2021/9/8 08:07
 * @Description:
 */
public class Solution_113 {
    List<List<Integer>> ans = new LinkedList();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null){
            return ans;
        }
        return pathSum1(root,targetSum,new ArrayList<Integer>());
    }
    public List<List<Integer>> pathSum1(TreeNode root, int targetSum,List<Integer> list){
        if (root.left == null && root.right == null){
            if (root.val == targetSum){
                list.add(root.val);
                ans.add(new ArrayList<>(list));
                list.remove(list.size() - 1);
            }
            return ans;
        }
        list.add(root.val);
        if (root.left != null){
            pathSum1(root.left,targetSum - root.val,list);

        }
        if (root.right != null)
        {
            pathSum1(root.right,targetSum - root.val,list);
        }
        list.remove(list.size() - 1);
        return ans;
    }
}
